package algocasts;

import java.util.Stack;

public class P129_ValidateStackSequences {
    // Time: O(n)  Space: O(n)
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed == null || popped == null || popped.length != pushed.length)
            return false;
        Stack<Integer> stack = new Stack<>();
        int p = 0;
        for (int num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popped[p]) {
                stack.pop();
                ++p;
            }
        }
        return stack.isEmpty();
    }

    // Time: O(n)  Space: O(n)
    public boolean validateStackSequences_Array(int[] pushed, int[] popped) {
        if (pushed == null || popped == null || popped.length != pushed.length)
            return false;
        int[] stack = new int[pushed.length];
        int p = 0, top = -1;
        for (int num : pushed) {
            stack[++top] = num;
            while (top != -1 && stack[top] == popped[p]) {
                --top;
                ++p;
            }
        }
        return top == -1;
    }
}
